//合并两个排序的链表
//递归解决
//终止条件：两链表其中一个返回空时，返回另一个链表
//若 list1.val <= list2.val 将较小的list1.next与merge后的表头连接
//即list1.next = Merge(list1.next,list2);
//每次返回值是排序好的链表头
public class MergeSortedLists {

    public ListNode Merge(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        } else if (list2 == null) {
            return list1;
        }
        if (list2.val >= list1 .val) {
            list1.next = Merge(list1.next, list2);
            return list1;
        } else {
            list2.next = Merge(list1, list2.next);
            return list2;
        }
    }

}
